
为了使用AST生成SSA形式的IR代码，可以使用一种称为AST编号的方法。基本思想是，对于每个基本块，我们存储写入该基本块中局部变量的当前值。

\begin{myNotic}{Note}
实现基于Braun et al.的论文《Simple and Efficient Construction of Static Single Assignment Form》，International Conference on CompilerConstruction 2013 (CC 2013)， Springer(见\url{http://individual.utoronto.ca/dfr/ece467/braun13.pdf})。在其呈现的形式中，仅适用于具有结构化受控流的IR代码。若需要支持任意控制流，本文还描述了必要的扩展——例如：goto。
\end{myNotic}

虽然很简单，但仍然需要几个步骤。首先介绍所需的数据结构，然后了解如何在基本块的局部读写值。然后，将处理几个基本块中使用的值，并通过优化创建的phi指令来结束。

\mySubsubsection{4.2.1.}{定义数据结构保存值}

使用BasicBlockDef struct来保存单个块的信息:

\begin{cpp}
struct BasicBlockDef {
    llvm::DenseMap<Decl *, llvm::TrackingVH<llvm::Value>> Defs;
    // ...
};
\end{cpp}

llvm::Value类表示SSA格式的值，其作用类似于计算结果的标签。通过IR指令创建，然后使用。优化过程中可能会发生各种变化，若优化器检测到\%1和\%2的值始终相同，可将\%2替换为\%1。这会改变标签，但不会改变计算。

为了了解这些变化，不能直接使用Value类。相反，这时需要一个值句柄。Value的处理有不同的功能。为了跟踪替换，需要使用llvm::TrackingVH<>类，所以Defs成员将AST的声明(变量或正式参数)映射到其当前值，需要为每个基本块存储这些信息:

\begin{cpp}
llvm::DenseMap<llvm::BasicBlock *, BasicBlockDef> CurrentDef;
\end{cpp}

有了这个数据结构，就可以处理局部值了。

\mySubsubsection{4.2.2.}{定义保存值的数据结构}

为了在基本块中存储局部变量的当前值，将在map中创建一个条目:

\begin{cpp}
void writeLocalVariable(llvm::BasicBlock *BB, Decl *Decl,
                        llvm::Value *Val) {
    CurrentDef[BB].Defs[Decl] = Val;
}
\end{cpp}

因为值可能不在基本块中，所以变量值的查找有点复杂，所以需要使用可能的递归搜索将搜索扩展到前面的节点:

\begin{cpp}
llvm::Value *
readLocalVariable(llvm::BasicBlock *BB, Decl *Decl) {
    auto Val = CurrentDef[BB].Defs.find(Decl);
    if (Val != CurrentDef[BB].Defs.end())
        return Val->second;
    return readLocalVariableRecursive(BB, Decl);
}
\end{cpp}

实际的工作是搜索前面的块，将在下一节中实现。

\mySubsubsection{4.2.3.}{前块中搜索值}

若正在查看的当前基本块只有一个前块，则直接在那里搜索变量值。若基本块有多个前块，需要在所有这些块中搜索值并组合结果。为了说明这种情况，可以看看前一节中使用WHILE条件语句的基本块。

这个基本块有两个前块——一个来自WHILE语句之前的语句，另一个来自WHILE循环主体末尾的分支。在条件中使用的变量应该有一些初始值，并且最有可能在循环体中更改，所以需要收集这些定义并创建phi指令。从WHILE语句创建一个包含循环的基本块。

因为需要递归地搜索前块，所以必须打破这种循环。可以使用一个简单的技巧:插入一个空的phi指令，并将其记录为变量的当前值。若在搜索中再次看到这个基本块，则看到该变量有一个可以使用的值，搜索到这里就停止了。当收集了所有的值，就必须更新phi指令。

然而，我们仍然会面临一个问题。在查找的时候，并不是一个基本块的所有前块都已知。来看看为WHILE语句创建的基本块，首先生成循环条件的IR，但只有在主体的IR生成之后，才能添加从主体末尾返回到包含条件基本块的分支(这是因为这个基本块之前是未知的)。若需要在条件中读取变量的值，那就卡住了，因为不是所有的前块都已知。

为了解决这个问题，必须做点什么:

\begin{enumerate}
\item
首先，必须在基本块上添加一个密封(Sealed)标志。

\item
然后，若知道基本块的所有前块，必须将基本块定义为密封。若基本块没有密封，并且需要查找这个基本块中尚未定义变量的值，必须插入一个空的phi指令，并将其作为值。

\item
也需要记住这个指令。若块稍后密封，则需要用实际值更新指令。为了实现这一点，必须在结构体BasicBlockDef中添加两个成员:IncompletePhis映射，记录了稍后需要更新的phi指令，以及Sealed标志，这表示基本块是否密封:

\begin{cpp}
llvm::DenseMap<llvm::PHINode *, Decl *> IncompletePhis;
unsigned Sealed : 1;
\end{cpp}

\item
该方法的实现，如本节开头所讨论:

\begin{cpp}
llvm::Value *CGProcedure::readLocalVariableRecursive(
        llvm::BasicBlock *BB, Decl *Decl) {
    llvm::Value *Val = nullptr;
    if (!CurrentDef[BB].Sealed) {
        llvm::PHINode *Phi = addEmptyPhi(BB, Decl);
        CurrentDef[BB].IncompletePhis[Phi] = Decl;
        Val = Phi;
    } else if (auto *PredBB = BB->getSinglePredecessor()) {
        Val = readLocalVariable(PredBB, Decl);
    } else {
        llvm::PHINode *Phi = addEmptyPhi(BB, Decl);
        writeLocalVariable(BB, Decl, Phi);
        Val = addPhiOperands(BB, Decl, Phi);
    }
    writeLocalVariable(BB, Decl, Val);
    return Val;
}
\end{cpp}

\item
addEmptyPhi()方法在基本块的开头插入一个空的phi指令:

\begin{cpp}
llvm::PHINode *
CGProcedure::addEmptyPhi(llvm::BasicBlock *BB,
        Decl *Decl) {
    return BB->empty()
        ? llvm::PHINode::Create(mapType(Decl), 0,
                                "", BB)
        : llvm::PHINode::Create(mapType(Decl), 0,
                                "", &BB->front());
}
\end{cpp}

\item
要将缺失的操作数添加到phi指令中，必须首先搜索基本块的所有前块，并将操作数值对和基本块添加到phi指令中，需要尝试优化指令:

\begin{cpp}
llvm::Value *
CGProcedure::addPhiOperands(llvm::BasicBlock *BB,
                            Decl *Decl,
                            llvm::PHINode *Phi) {
    for (auto *PredBB : llvm::predecessors(BB))
        Phi->addIncoming(readLocalVariable(PredBB, Decl),
                         PredBB);
    return optimizePhi(Phi);
}
\end{cpp}

\end{enumerate}

该算法可以产生不必要的phi指令，有种方法可以用来进行优化，这将在下一节中实现。

\mySubsubsection{4.2.4.}{优化生成的phi指令}

如何优化指令，为什么要这样做?尽管SSA形式对许多优化都有利，但算法通常不能解析phi指令，从而阻碍了优化，所以生成的phi指令越少越好:

\begin{enumerate}
\item
若指令只有一个操作数，或者所有操作数的值都相同，则用这个值替换指令。若该指令没有操作数，则用特殊的Undef值替换该指令。只有当指令有两个或更多不同的操作数时，才必须保留这条指令:

\begin{cpp}
llvm::Value *
CGProcedure::optimizePhi(llvm::PHINode *Phi) {
    llvm::Value *Same = nullptr;
    for (llvm::Value *V : Phi->incoming_values()) {
        if (V == Same || V == Phi)
            continue;
        if (Same && V != Same)
            return Phi;
        Same = V;
    }
    if (Same == nullptr)
        Same = llvm::UndefValue::get(Phi->getType());
\end{cpp}


\item
删除一条phi指令可能会给其他phi指令带来优化机会，LLVM会跟踪用户和值的使用(即SSA定义中提到的use-def链)，必须在其他phi指令中搜索该值使用情况，并尝试优化这些指令:

\begin{cpp}
    llvm::SmallVector<llvm::PHINode *, 8> CandidatePhis;
    for (llvm::Use &U : Phi->uses()) {
        if (auto *P =
                llvm::dyn_cast<llvm::PHINode>(U.getUser()))
        if (P != Phi)
            CandidatePhis.push_back(P);
    }
    Phi->replaceAllUsesWith(Same);
    Phi->eraseFromParent();
    for (auto *P : CandidatePhis)
        optimizePhi(P);
    return Same;
}
\end{cpp}

\end{enumerate}

还可以进一步改进这个算法，可以选择并记住两个不同的值，而不是总是迭代每个phi指令的值列表。在optimizePhi函数中，可以检查这两个值是否仍然在phi指令的列表中，则没必要优化。但即使没有这个优化，这个算法也可以运行得也很快，所以现在不进行实现。

现在，唯一没有做的是实现密封基本块的操作。

\mySubsubsection{4.2.5.}{密封块}

了解了一个区块的所有前块，就可以密封这个块了。若语言只包含结构化语句(如tinylang)，那么很容易确定块的位置。再看一下为WHILE语句生成的基本块。

包含条件的基本块可以在主体的末端添加分支后进行密封，这是缺少的最后一个前块。要密封一个块，可以简单地将缺失的操作数，添加到不完整的phi指令中并设置标志:

\begin{cpp}
void CGProcedure::sealBlock(llvm::BasicBlock *BB) {
    for (auto PhiDecl : CurrentDef[BB].IncompletePhis) {
        addPhiOperands(BB, PhiDecl.second, PhiDecl.first);
    }
    CurrentDef[BB].IncompletePhis.clear();
    CurrentDef[BB].Sealed = true;
}
\end{cpp}

有了这些方法，就可以为表达式生成IR了。

\mySubsubsection{4.2.6.}{生成表达式的IR}

要翻译表达式，如第2章所示。唯一有趣的部分是如何访问变量。上一节讨论了局部变量，但还要考虑其他类型的变量。这里，就讨论一下接下来需要些做什么:

\begin{itemize}
\item
对于过程的局部变量，使用上一节中的readLocalVariable()和writeLocalVariable()方法。

\item
对于一个封闭过程中的局部变量，需要一个指向封闭过程框架的指针。这将在本章稍后的章节中进行处理。

\item
对于全局变量，生成加载和存储指令。

\item
对于形式参数，必须区分按值传递和按引用传递(tinylang中的VAR参数)。通过值传递的参数会视为局部变量，通过引用传递的参数会当作全局变量。
\end{itemize}

综上所述，得到如下用于读取变量或形参的代码:

\begin{cpp}
llvm::Value *CGProcedure::readVariable(llvm::BasicBlock *BB,
Decl *D) {
    if (auto *V = llvm::dyn_cast<VariableDeclaration>(D)) {
        if (V->getEnclosingDecl() == Proc)
            return readLocalVariable(BB, D);
        else if (V->getEnclosingDecl() == CGM.getModuleDeclaration()) {
            return Builder.CreateLoad(mapType(D),
            CGM.getGlobal(D));
        } else
        llvm::report_fatal_error("Nested procedures not yet supported");
    } else if (auto *FP = llvm::dyn_cast<FormalParameterDeclaration>(D)) {
        if (FP->isVar()) {
            return Builder.CreateLoad(mapType(FP, false),
            FormalParams[FP]);
        } else
        return readLocalVariable(BB, D);
    } else
        llvm::report_fatal_error("Unsupported declaration");
}
\end{cpp}

对变量或形式参数的写入是对称的——需要将要读的方法与要写的方法交换，并使用存储指令，而非加载指令。

接下来，在为这些函数生成IR代码时，应用这些函数。

\mySubsubsection{4.2.7.}{生成函数的IR}

大多数IR代码都存在于函数中，IR代码中的函数类似于C语言中的函数，通过名称、参数类型、返回值和其他属性指定。要调用不同编译单元中的函数，需要声明该函数，这与C语言中的原型类似。若向函数中添加基本块，就可以定义函数。接下来的几节会介绍这些内容，但首先要讨论的是，符号名称的可见性。


\mySubsubsection{4.2.8.}{通过链接和名称修改控制可见性}

函数(以及全局变量)具有附加的链接样式。使用链接方式，我们定义了符号名称的可见性，若多个符号具有相同的名称会发生什么。最基本的链接样式是私有的和外部的，私有链接的符号仅在当前编译单元中可见，而具有外部链接的符号则全局可见。

对于没有模块概念的语言(如C语言)，这是足够的。对于模块，需要做更多的事情。假设有一个模块Square，提供了一个Root()函数，还有一个模块Cube，也提供了一个Root()函数。若函数私有，那么没什么问题，该函数获取名称Root和私有链接。若导出函数，以便可以从其他模块调用它，情况就不同了。因为函数名不唯一，所以仅使用函数名就不够了。

解决方案是调整名称使其全局唯一，这称为名称修改，如何做到取决于语言的要求和特点。在我们的示例中，基本思想是使用模块名和函数名的组合来创建全局唯一的名称。使用Square.Root作为名称看起来是一个显而易见的解决方案，但这可能会导致汇编程序的问题，因为点可能具有特殊的含义。不需要在名称组件之间使用分隔符，可以通过在名称组件前加上长度:6Square4Root来获得类似的效果。单这不是LLVM的合法标识符，我们可以通过在整个名称前加上\_t (t表示tinylang)来修复这个问题:\_t6Square4Root。通过这种方式，可以为导出符号创建唯一名称:

\begin{cpp}
std::string CGModule::mangleName(Decl *D) {
    std::string Mangled("_t");
    llvm::SmallVector<llvm::StringRef, 4> List;
    for (; D; D = D->getEnclosingDecl())
        List.push_back(D->getName());
    while (!List.empty()) {
        llvm::StringRef Name = List.pop_back_val();
        Mangled.append(llvm::Twine(Name.size()).concat(Name).str());
    }
    return Mangled;
}
\end{cpp}

若语言支持类型重载，则需要使用类型名扩展此方案。例如，C++中中要区分int root(int)和double root(double)函数，必须将形参类型和返回值添加到函数名中。还需要考虑生成的名称的长度，因为某些链接器对长度进行了限制。在C++中使用嵌套的命名空间和类，修改后的名称可能相当长。

这里，C++定义了一个压缩方案，以避免一遍又一遍地重复名称组件。

接下来，就来看看如何处理函数参数。

\mySubsubsection{4.2.9.}{AST描述类型转换为LLVM类型}

函数的参数也需要考虑。首先，需要将源语言的类型映射到LLVM类型。由于tinylang目前只有两种类型，所以很容易:

\begin{cpp}
llvm::Type *CGModule::convertType(TypeDeclaration *Ty) {
    if (Ty->getName() == "INTEGER")
        return Int64Ty;
    if (Ty->getName() == "BOOLEAN")
        return Int1Ty;
    llvm::report_fatal_error("Unsupported type");
}
\end{cpp}

Int64Ty、Int1Ty和VoidTy是类成员，包含i64、i1和void LLVM类型的类型表示。

对于通过引用传递的形参，这是不够的。该参数的LLVM类型为指针型，当我们想要使用形参的值时，需要知道底层类型。这由HonorReference标志控制，其默认值为true。我们对函数进行推广，并考虑形参:

\begin{cpp}
llvm::Type *CGProcedure::mapType(Decl *Decl,
                                 bool HonorReference) {
    if (auto *FP = llvm::dyn_cast<FormalParameterDeclaration>(
    Decl)) {
        if (FP->isVar() && HonorReference)
        return llvm::PointerType::get(CGM.getLLVMCtx(),
        /*AddressSpace=*/0);
        return CGM.convertType(FP->getType());
    }
    if (auto *V = llvm::dyn_cast<VariableDeclaration>(Decl))
        return CGM.convertType(V->getType());
    return CGM.convertType(llvm::cast<TypeDeclaration>(Decl));
}
\end{cpp}

有了这些辅助程序，我们就可以创建LLVM IR函数了。

\mySubsubsection{4.2.10.}{创建LLVM IR函数}

要在LLVM IR中生成一个函数，需要一个函数类型，这类似于C中的原型。创建函数类型包括映射类型，然后使用工厂方法来创建函数类型:

\begin{cpp}
llvm::FunctionType *CGProcedure::createFunctionType(
ProcedureDeclaration *Proc) {
    llvm::Type *ResultTy = CGM.VoidTy;
    if (Proc->getRetType()) {
        ResultTy = mapType(Proc->getRetType());
    }
    auto FormalParams = Proc->getFormalParams();
    llvm::SmallVector<llvm::Type *, 8> ParamTypes;
    for (auto FP : FormalParams) {
        llvm::Type *Ty = mapType(FP);
        ParamTypes.push_back(Ty);
    }
    return llvm::FunctionType::get(ResultTy, ParamTypes,
                                    /*IsVarArgs=*/false);
}
\end{cpp}

根据函数类型，我们还创建了LLVM函数。这将函数类型与链接修改后的名称进行了关联:

\begin{cpp}
llvm::Function *
CGProcedure::createFunction(ProcedureDeclaration *Proc,
                            llvm::FunctionType *FTy) {
    llvm::Function *Fn = llvm::Function::Create(
        Fty, llvm::GlobalValue::ExternalLinkage,
        CGM.mangleName(Proc), CGM.getModule());
\end{cpp}

getModule()方法返回当前的LLVM模块，稍后我们将对其进行设置。

创建了函数后，可以添加更多关于它的信息:

\begin{itemize}
\item
首先，可以给出参数的名称，可使得IR更具可读性。

\item
其次，可以给函数和参数添加属性来指定一些特征。例如，通过引用传递的参数进行此操作。
\end{itemize}

在LLVM级别，这些参数是指针。但是从源语言设计来看，这些是非常受限的指针。与C++中的引用类似，总是需要为VAR参数指定一个变量。根据设计，我们知道这个指针永远不会为空，并且始终可解引用，所以可以读取指向的值，而不会有风险。而且，该指针不能传递——特别是，因为没有比函数调用更长的指针副本，所以不能捕获指针。

llvm::AttributeBuilder类用于为形式参数构建属性集。要获取参数类型的存储大小，可以简单地查询数据布局对象:

\begin{cpp}
    for (auto [Idx, Arg] : llvm::enumerate(Fn->args())) {
        FormalParameterDeclaration *FP =
            Proc->getFormalParams()[Idx];
        if (FP->isVar()) {
            llvm::AttrBuilder Attr(CGM.getLLVMCtx());
            llvm::TypeSize Sz =
                CGM.getModule()->getDataLayout().getTypeStoreSize(
                    CGM.convertType(FP->getType()));
            Attr.addDereferenceableAttr(Sz);
            Attr.addAttribute(llvm::Attribute::NoCapture);
            Arg.addAttrs(Attr);
        }
        Arg.setName(FP->getName());
    }
    return Fn;
}
\end{cpp}

这样，就创建了IR函数。下一节中，我们将把函数体的基本块添加到函数中。

\mySubsubsection{4.2.11.}{生成函数体}

我们几乎完成了为函数生成IR代码，只需要把这些片段组合在一起就可以生成函数了，包括它的函数体:

\begin{enumerate}
\item
给定一个来自tinylang的过程声明。首先，将创建函数类型和函数:

\begin{cpp}
void CGProcedure::run(ProcedureDeclaration *Proc) {
    this->Proc = Proc;
    Fty = createFunctionType(Proc);
    Fn = createFunction(Proc, Fty);
\end{cpp}

\item
接下来，将创建函数的第一个基本块，并使其成为当前块:

\begin{cpp}
    llvm::BasicBlock *BB = llvm::BasicBlock::Create(
        CGM.getLLVMCtx(), "entry", Fn);
    setCurr(BB);
\end{cpp}

\item
然后，必须逐一检查所有的形参。为了正确处理VAR参数，需要初始化FormalParams成员(在readVariable()中使用)。与局部变量相比，形参在第一个基本块中有一个值，所以些值必须已知:

\begin{cpp}
    for (auto [Idx, Arg] : llvm::enumerate(Fn->args())) {
        FormalParameterDeclaration *FP =
            Proc->getFormalParams()[Idx];
        FormalParams[FP] = &Arg;
        writeLocalVariable(Curr, FP, &Arg);
    }
\end{cpp}

\item
设置之后，可以调用emit()方法来生成IR代码:

\begin{cpp}
    auto Block = Proc->getStmts();
    emit(Proc->getStmts());
\end{cpp}

\item
生成IR代码后的最后一个块可能还没有密封，所以现在必须调用sealBlock()。tinylang中的过程可能有隐式返回，因此必须检查最后一个基本块是否有正确的结束符；否则，需要添加一个结束符:

\begin{cpp}
    if (!Curr->getTerminator()) {
        Builder.CreateRetVoid();
    }
    sealBlock(Curr);
}
\end{cpp}

\end{enumerate}

至此，我们已经完成了为函数生成IR代码的工作。但仍然需要创建LLVM模块，它将所有IR代码整合在一起。我们将在下一节中进行此操作。








